package medium

import (
	. "GoLeetcode/common"
)

/*
时间复杂度：O(N)
空间复杂度：O(N)

动态规划

难点：有正数和负数两种状态，如何通过者两种状态构建动态规划关系
解决:
设positive[i]表示以i结尾的乘积为正数的最长子数组长度
negative[i]表示以i结尾的乘积为负数的最长子数组长度
每次求得的positive[i]和negative[i]再求最大即可
*/

func getMaxLen(nums []int) int {
	positive := make([]int, len(nums)+1)
	negative := make([]int, len(nums)+1)
	maxLen := 0
	for i, v := range nums {
		if v == 0 {
			positive[i+1] = 0
			negative[i+1] = 0
		} else if v > 0 {
			positive[i+1] = positive[i] + 1
			if negative[i] > 0 {
				negative[i+1] = negative[i] + 1
			}
		} else {
			if negative[i] > 0 {
				positive[i+1] = negative[i] + 1
			}
			negative[i+1] = positive[i] + 1
		}
		maxLen = Max(maxLen, positive[i+1])
	}
	return maxLen
}

/*
时间复杂度：O(N)
空间复杂度：O(1)

贪心
*/

func getMaxLen1(nums []int) int {
	positive, negative := 0, 0
	maxLen := 0
	for _, v := range nums {
		if v > 0 {
			if negative > 0 {
				// v>0, negative <0, 正负得负
				negative = negative + 1
			} else {
				negative = 0
			}
			positive = positive + 1
		} else if v < 0 {
			t := positive
			if negative > 0 {
				// v < 0, negative < 0; 负负得正
				positive = negative + 1
			} else {
				positive = 0
			}
			negative = t + 1
		} else {
			positive = 0
			negative = 0
		}
		maxLen = Max(maxLen, positive)
	}
	return maxLen
}
